package leetcode.code600;

public class Solution4 extends Solution600 {
	@Override
	public int findIntegers(int n) {
		int len = Integer.toBinaryString(n).length();
		int[][] array = new int[31][5];
		array[1][0] = 2;// 1位二级制数，有几个满足条件的
		array[1][1] = 0;// 满足条件的最小数字
		array[1][2] = 1;// 这一位的最大数
		array[1][3] = 2;// 这和这之前一共有几个，满足条件的
		array[1][4] = 1;// 满足条件的最大数字
		array[2][0] = 1;
		array[2][1] = 2;
		array[2][2] = 3;
		array[2][3] = 3;// 这和这之前一共有几个
		array[2][4] = 2;// 最大满足需求的数
		for (int i = 3; i < len + 1; i++) {
			array[i][0] = array[i - 2][3];// 取决于i-2和i-2之前
			array[i][1] = (1 << (i - 1));
			array[i][2] = (1 << i) - 1;
			array[i][3] = array[i][0] + array[i - 1][3];
			array[i][4] = (array[i - 1][4] & 1) == 1 ? array[i - 1][4] << 1 : (array[i - 1][4] << 1) | 1;
		}
		int sum = array[len - 1][3];
		int start = array[len][1];
		int end = array[len][2];
		int down = 2;
		while (start <= end && start <= n) {
			int downTo = len - down;
			if (downTo > 0) {// 尽量夹到低位结果范围内，能加夹出来最好
				int temp = start | array[downTo][4];
				if (temp <= n) {
					sum += array[downTo][3];
					if (temp <= n && down == 2) {
						return sum;
					}
					int aimLevel = downTo + 1;
					start = start | array[aimLevel][1];
					len = aimLevel;
					down = 2;
				} else {
					end = temp;
					down++;
				}
			} else {// 不能夹就数数，这块可以替换成码表的，对应数组不能构建的0，1，2
				sum++;
				int temp = start;
				int count1 = 0;
				while (temp > 0) {
					if ((temp & 1) == 1) {
						count1++;
					} else if (count1 > 0) {
						count1--;
					}
					if (count1 == 2) {
						--sum;
						break;
					}
					temp >>>= 1;
				}
				start++;
			}
		}
		return sum;
	}

	public static void main(String[] args) {
		Solution4 so = new Solution4();
//		so.debug1();
//		so.debug2();
//		so.debug3();
		int n = 20;// 1000000000
		int r = so.findIntegers(n);
//		test(n);
		System.out.println("r " + r);
//		System.out.println(0 >> 1);
	}

	public static void test(int size) {
		size += 5;
		int col1 = String.valueOf(size).length() + 1;
		int col2 = Integer.toBinaryString(size).length() + 1;
		for (int i = 0; i < size; i++) {
			myPrint(i, col1, Integer.toBinaryString(i), col2);
		}
	}

	public static void myPrint(Object... objects) {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < objects.length; i += 2) {
			sb.append(tail(String.valueOf(objects[i]), Integer.valueOf(String.valueOf(objects[i + 1]))));
		}
		System.out.println(sb.toString());
	}

	public static String tail(String s, int max) {
		int blank = max - s.length();
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < blank; i++) {
			sb.append(' ');
		}
		sb.append(s);
		return sb.toString();
	}

}
